package com.fantaike.algorithm.sort;

/**
 * 希尔排序：希尔排序是插入排序的进阶版，插入排序的时间复杂打是O(n^2)，当数据量很大的时候，效率就会变得非常
 * 低。插入排序是将未分组的数组依次和以分组的数组倒叙进行比较，这就会效率变得很低，所以，就出现希尔排序，根据
 * 增量当作分组的依据，之后对分组后的每一组按照插入排序的规则进行排序。
 * @author jishushen
 * @create 2021-08-01 13:30
 */
public class Shell {

    /**
     * @Description: 希尔排序
     * @param array
     * @Date: 2021/8/1 15:21
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void sort(Comparable[] array){
        //1.要确定增量 h
        int h = 1;
        while (h < array.length / 2){
            h = 2 * h + 1;
        }
        //2.希尔排序
        while (h >= 1){
            //排序,未分组的数组初始值就在增量h处
            for (int i = h; i < array.length; i++) {
                /*
                    根据增量h进行分组，将分组后的依次比较
                    未分组的数组初始值就在增量h处,而分组的初始值会在j-h处，每次的间隔都是h
                    所以循环第二个参数为 j>=h
                */
                for (int j = i; j >= h; j -= h) {
                    //比较,array[j-h]和array[j],如果array[j-h]数据大就交换
                    if (greater(array[j - h], array[j])) {
                        exch(array, j - h, j);
                    } else {
                        //以确定了位置，结束循环
                        break;
                    }
                }
            }
            //增量h 按照一定顺序进行递减
            h = h / 2;
        }
    }

    /**
     * @Description: v和w进行比较，如果v比w大就返回true
     * @param v
     * @param w
     * @Date: 2021/7/31 13:46
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }

    /**
     * @Description: 索引i处的值和索引j处的值进行交换
     * @param array
     * @param i
     * @param j
     * @Date: 2021/7/31 13:48
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void exch(Comparable[] array,int i,int j){
        Comparable temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}
